package com.list;

import com.tree.TreeNode;

public class Test1 {
    //合并两个链
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode pump = new ListNode(-1),p=pump;
        ListNode p1=l1,p2=l2;
        while (p1!=null&&p2!=null){
            if (p1.val< p2.val){
                p.next=p1;
                p1=p1.next;
            }else {
                p.next=p2;
                p2=p2.next;
            }
            p=p.next;
        }
        if (p1!=null){
            p.next=p1;
        }
        if (p2!=null){
            p.next=p2;
        }
        return pump.next;

    }
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2){
       if (l1==null){
           return l2;
       }else if (l2==null){
           return l1;
       }else if (l1.val<l2.val){
           l1.next=mergeTwoLists2(l1.next,l2);
           return l1;
       }else {
           l2.next=mergeTwoLists2(l2.next,l1);
           return l2;
       }
    }
    public ListNode rotateRight(ListNode head, int k) {
        if (head==null){
            return null;
        }
        int n=0;
        ListNode tail=null;//尾节点
        for (ListNode p=head;p!=null;p=p.next){
            n++;
        tail=tail.next;
        }
        k=k%n;
        ListNode p=head;
        for (int i=0;i<n-k-1;i++){
            p=p.next;
        }
        tail.next=head;
        head=p.next;
        p.next=null;
        return head;
    }
    public static ListNode reverseList(ListNode head){
       /* ListNode cur=head;
        ListNode temp;
        ListNode pre;
        while (cur!=null){
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;*/
      /*  ListNode pc=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode next=cur.next;
            cur.next=pc;
            pc=cur;
            cur=next;
        }
        return pc;*/
        if (head==null||head.next==null){
            return head;
        }
        ListNode p=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return p;
    }
    //存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
    //
    //返回同样按升序排列的结果链表。
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null) {
        return head;
        }

        ListNode cur=head;
        while (cur.next!=null){
            if (cur.next.val==cur.val){
                cur.next=cur.next.next;
            }else {
                cur=cur.next;
            }

        }
        return head;
    }

    public ListNode deleteDuplicates3(ListNode head) {
        if (head==null){
            return null;
        }

        ListNode node = new ListNode(0, head);
        ListNode cu=node;

        while (cu.next!=null&&cu.next.next!=null){
            if (cu.next.val==cu.next.next.val){
                int x=cu.next.val;
                while (cu.next!=null&&cu.next.val==x){
                    cu.next=cu.next.next;
                }
            }else {
                cu=cu.next;
            }
        }
        return node.next;
    }
    public ListNode reverseBetween(ListNode head, int left, int right) {

        ListNode pre = new ListNode(0);
        pre.next=head;
        ListNode dump=pre;
        for (int i = 0; i < left-1; i++) {
            dump=dump.next;
        }
        ListNode cur=dump.next;
        for (int i = 0; i < right-left; i++) {
            ListNode next=cur.next;
            cur.next=cur.next.next;
            next.next=dump.next;
            dump.next=next;

        }
        return pre.next;    }
    public TreeNode sortedListToBST(ListNode head) {
        //终止条件
        if (head==null){
            return null;
        }
        if (head.next==null){
            return new TreeNode(head.val);
        }
        ListNode slow=head,fast=head,pre=head;
        while (fast!=null||fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        TreeNode root=new TreeNode(slow.val);
        root.left=sortedListToBST(head);
        root.right=sortedListToBST(slow.next);
        return root;
    }
    //给你一个链表的头节点 head ，判断链表中是否有环
    public boolean hasCycle(ListNode head) {
        if (head==null||head.next==null){
            return false;
        }


        ListNode fast=head.next;
        ListNode slow=head;
        while (fast!=slow){
            if (fast==null||fast.next==null)
                return false;
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }

}


